perm filename NOTES.C[1,RWF]2 blob
sn#482708 filedate 1979-10-15 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00028 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00004 00002 This is file FLOYD.C[1,PHY] at the Stanford AI Lab (SU-AI), last written
C00006 00003 PROCEDURE NAME(...) BEGIN
C00008 00004 Example:
C00010 00005 APPENDIX J. FILE SPECIFICATIONS [D4].
C00013 00006 HOW TO TALK ABOUT SETS OF FILES:
C00017 00007 Some less useful things control characters do:
C00018 00008 APPENDIX K. COMMON PROGRAMMING ERRORS.
C00023 00009 (21) Conditional expressions without alternative: A := IF B THEN C+D .
C00024 00010 Examples follow, showing typical error messages resulting from common SAIL
C00026 00011 We shall show the effects of making changes that leave the program
C00029 00012 The first error causes multiple error messages, all at places where COL is
C00033 00013 BLOCK FOUND WHILE FLUSHING STATEMENT - WILL TRY TO PARSE IT.
C00036 00014 The second message correctly diagnosed the problem. The compiler soon got
C00039 00015 APPENDIX L. FINDING THE ROOT OF AN EQUATION.
C00042 00016 APPENDIX M. POLYNOMIAL MULTIPLICATION.
C00045 00017 BEGIN "MAIN"
C00047 00018 [Into SAIL notes, insert before CONVERSION OF STRINGS TO NUMBERS.]
C00049 00019 (4) To remove initial, final, and multiple spaces from a string S :
C00051 00020 APPENDIX N. Number Representation on DEC System-20 and Relations to SAIL.
C00055 00021 Negative numbers have a sign bit of 1 and are stored in what is called
C00059 00022 2. %Real Numbers%.
C00064 00023 We now give the floating-point representation of some sample numbers. As we
C00068 00024 Notice that in checking the negative numbers one can take the two's complement
C00072 00025 -27
C00077 00026 When a real value is assigned to an integer variable or vice versa, automatic
C00081 00027 RANDOM NUMBERS.
C00084 00028 For a normally distributed number (this distribution is the bell-shaped
C00088 ENDMK
C⊗;
This is file FLOYD.C[1,PHY] at the Stanford AI Lab (SU-AI), last written
July 31, 1978. Bob Floyd (aka RWF at SAIL, R.RWF at LOTS) wrote it, maintains
it, and welcomes suggestions.
APPENDIX I. A DISCIPLINE OF PUNCTUATION AND INDENTATION FOR SAIL COMMANDS.
If you have trouble remembering where the semicolons go, use this method, which
uses more blocks than are absolutely necessary, but which is easy to read and
to write correctly.
All primitive commands are written with a semicolon at the end of the line.
All composite commands are written in one of these forms:
FOR ... DO BEGIN
C1
C2
.
.
.
Cn
END;
WHILE ... DO BEGIN
C1
C2
.
.
.
Cn
END;
IF ... THEN BEGIN
C1
C2
.
.
.
Cn
END;
IF ... THEN BEGIN
C1
C2
.
.
.
Cn
END ELSE BEGIN
Cn+1
Cn+2
.
.
.
Cm
END;
PROCEDURE NAME(...); BEGIN
C1
C2
.
.
.
Cn
END;
CASE ... OF BEGIN
[1] C1
[2] C2
[3] C3
.
.
.
[n] Cn (it is essential not to end this line
END; with a semicolon)
DO BEGIN
C1
C2
.
.
.
Cn
END UNTIL E;
Under this discipline all commands (except the last in a CASE statement)
end with a semicolon, which you can think of as part of the command. The
command to do nothing is just the semicolon by itself. All the component
commands of a composite command are indented more than the first and last
lines; by looking straight down from the first line, you find the matching
last line, starting with END.
Comments are written before the command at the same level of indentation as
its first line. Every line ends with either a semicolon, or the word BEGIN.
The system is flexible; when additions or deletions are made, you don't have
to change other lines.
Example:
COMMENT ROOK ON CHESSBOARD;
BEGIN "MAIN";
REQUIRE "<C.CS10X>INTRO.HDR" SOURCE!FILE;
INTEGER ROOKROW, ROOKCOL, ROW, COL;
ROOKROW := READ;
WHILE ROOKROW < 1 OR ROOKROW > 8 DO BEGIN
PRINT("TRY AGAIN");
ROOKROW := READ;
END;
PRINT("ROW =", ROOKROW);
ROOKCOL := READ;
WHILE ROOKCOL < 1 OR ROOKCOL > 8 DO BEGIN
PRINT("TRY AGAIN");
ROOKCOL := READ;
END;
PRINT("COLUMN =", ROOKCOL, NEWLINE);
COMMENT NOW PRINT BOARD;
FOR ROW UPTO 8 DO BEGIN "ROW"
FOR COL UPTO 8 DO BEGIN "COL"
IF ROW = ROOKROW THEN BEGIN "ONROW"
IF COL = ROOKCOL THEN BEGIN
PRINT("R");
END ELSE BEGIN
PRINT("*");
END
END "ONROW" ELSE BEGIN "OFFROW"
IF COL = ROOKCOL THEN BEGIN
PRINT("*");
END ELSE BEGIN
PRINT(".");
END;
END "OFFROW";
END "COL";
END "ROW";
END "MAIN";
APPENDIX J. FILE SPECIFICATIONS [D4].
The full specification of any file belonging to you is of the form
filename.filetype.generation
Use up to six letters and digits for the filename, chosen to help you
remember what the file is about. Use standard filetypes such as SAI,
according to the rules in File Types, below. The generation number will be
suppled automatically.
To refer to a file in someone else's directory [D4.3.1] , precede the
filename with his user name or directory name in angular brackets:
<s.smith>hisfilename.filetype.gen
You will find useful files in the directory <C.CS10X>
There are other kinds of file names with special meanings [D4.2].
File Types [D4.5]
SAI: a SAIL program
OUT: the output program from a program
DAT: input data for a program
TXT: text in English (or other human language)
TMP: a file which you want deleted when you log out
HDR: a header file for incorporation into programs
REL or BIN: a file in machine language
KNT: a file of execution counts, used by PROFIL
LST: a listing file, to be deleted after printing [D8.1.4]
DOC: documentation
CRF: a cross reference file [D8.2.4]
CMD: a file of TOPS-20 commands to happen automatically when you log in
[D3.2.4, D3.2.5]
CTL: a control file for a batch job [D3.4]
LOG: a log file for a batch job [D3.4]
EXE: an executable file in machine language [D8.1.5]
INI: a file of standard options to be used with EDIT, PRINT, and SUBMIT
[D7.4]
FOR: FORTRAN program
Files you create will usually be of types SAI, OUT, DAT, TXT, REL, or HDR.
HOW TO TALK ABOUT SETS OF FILES:
If you want to delete, print, list, see directory information about, etc.,
several files at once, you can name a subset of your files as follows. The
asterisk, * , stands for any file name, so @%PRINT$ *.SAI% will print
all your SAIL files. It also stands for any file type, so
@%DIRectory$ MYPROG.*.2%
will give you directory information about both MYPROG.SAI.2 and
MYPROG.OUT.2 . See [D4.8].
In most places where you would want to, you can give the names of a set of
files, separated by commas [D4.11], like
@%PRINT$ MYPROG.SAI, RESULTS.OUT%
Giving a file name alone is like following it with .* [D4.5].
If you don't mention a generation number, the system provides one as follows:
When you create a file, the generation number used is one more than the
highest existing generation of that file. When you read a file (editing,
compiling, printing etc.) the highest generation is used. When you delete
or undelete, all generations are used.
SOME USEFUL THINGS THAT CONTROL CHARACTERS DO (References are to DEC SYSTEM 20
OVERVIEW):
C (Twice) calls TOPS-20.
I Is the tab key.
O Stops, or restarts, output to the terminal, without stopping the
program that is running.
Q Looks at the next page of a multi-page terminal display.
S Stops the terminal display from moving, until Q restrarts it.
[D9.3.1]
T Gives load and usage statistics. [D7.6.3]
U Cancels current line (then hit RETURN).
W Deletes last word typed.
Z Signs off when entering data from terminal. In particular, used to
end a message you are mailing.
ESC Asks TOPS-20 to fill out the rest of a word for you if it can, and
prompt for the next word.
RUBOUT Deletes last character typed (so does BACKSPACE).
REPEAT While held down, makes other keys repeeeeeeeeeat.
SPACE Ends TOPS-20 operands.
? Asks for a list of available choices you can type next.
! Makes rest of the line a comment, ignored by TOPS-20.
Some less useful things control characters do:
E Stops people from sending you advice.
F Establishes single-field recognition for file names [D4.10].
G Rings the bell.
H Backspace.
L Form feed.
P Reverts to mini-Exec.
R Retypes the current line.
V Quote next character [D4.9].
[ Same as ESC.
BREAK Useless.
CLEAR (Upper case only) clears the screen.
APPENDIX K. COMMON PROGRAMMING ERRORS.
(1) Failure to have the same number of BEGINs and ENDs. With too many
ENDs there may be no error message. With too few, the likely message
is FATAL END OF SOURCE FILE at the end of the program. Omission of
BEGINs and ENDs is also likely to give rise to UNDECLARED IDENTIFIER
messages. To control this problm, it is advisable to label BEGINs
and ENDs, at least for the blocks of substantial size (about ten
lines).
(2) Omission of the semicolon. Symptoms: INSERTING FORGOTTEN SEMICOLON
or SYNTAX ERROR.
(3) Putting some of the commands of a block before some of the
declarations:
BEGIN
INTEGER N;
N := READ;
REAL ARRAY A[1:N];
.
.
.
END
(4) Omission of semicolon after comments. Symptom: usually loss of the
following command, often with no error message.
(5) Including spaces in combinations like := , <= , SOURCE!FILE ,
SETFORMAT .
(6) Omitting closing quote marks. Symptoms: many.
Example: PRINT("X =,X,"Y =",Y);
(7) Typing more than 80 characters per line. (This goes to a new line on
the terminal, but continues on the same line on paper listings of the
program, eventually spilling some of the program off the right edge of
the paper.)
(8) Forgetting to provide for spacing in output. Trying to print more
than 132 characters per line, and more than 60 lines per page.
(9) Running constants and identifiers together: PRINT(10000DIV X) .
(10) Omitting multiply signs: PRINT((A+B)(C-D),B**2-4AC) .
Symptom: UNDECLARED VARIABLE.
(11) Using unary minus after an operator without parenthesizing: A**-B .
(12) Failure to initialize variables used in an iteration. Failure to
initialize them often enough (at the right level of iteration).
(13) Using an integer variable to hold a quantity which may logically be
a non-integer:
INTEGER C;
C := SQRT(A**2 + B**2);
(14) Failure to prompt for input; to check it for validity; to reread
if invalid data are found; to echo all input in the output listing.
(15) Including semicolon just before ELSE.
(16) IF ... THEN C ELSE C ELSE C . Symptom: SYNTAX ERROR.
1 2 3
(17) Using = for := :
FOR I = 1 STEP 1 UNTIL 10 DO
A[I] = 3*I-1;
(18) Using := for = :
IF A := B THEN PRINT("YES") ELSE PRINT("NO")
(19) Patterns like WHILE X > Y THEN X := X-1 , IF P = Q DO PRINT(R) ,
REPEAT X := X-1 WHILE X > Y .
(20) Forgetting that many operations, such as MOD and DIV, assign their
arguments to integer variables before doing their work.
(21) Conditional expressions without alternative: A := IF B THEN C+D .
(22) Forgetting that, as data, upper and lower case letters are not
considered equal. Example:
PRINT("DO YOU WANT ...");
S := READLINE
IF EQU(S,"YES") THEN ... ELSE ...
Examples follow, showing typical error messages resulting from common SAIL
syntax errors.
The following is a correct SAIL program:
@TYPE (FILE) ROOK.SAI.3
00100 COMMENT ROOK ON CHESSBOARD;
00200 BEGIN "MAIN"
00300 REQUIRE "<C.CS10X>INTRO.HDR" SOURCE!FILE;
00400 INTEGER ROOKRO, ROOKCOL, ROW, COL;
00500
00600 ROOKROW := READ;
00700
00800 WHILE ROOKROW < 1 OR ROOKROW > 8 DO BEGIN
00900 PRINT("TRY AGAIN");
01000 ROOKROW := READ;
01100 END;
01200
01300 PRINT("ROW =", ROOKROW);
01400 ROOKCOL := READ;
01500
01600 WHILE ROOKCOL < 1 OR ROOKCOL > 8 DO BEGIN
01700 PRINT("TRY AGAIN");
01800 ROOKCOL := READ;
01900 END;
02000
02100 PRINT("COLUMN =", ROOKCOL, NEWLINE);
02200 COMMENT NOW PRINT BOARD;
02300
02400 FOR ROW UPTO 8 DO BEGIN "ROW"
02500 FOR COL UPTO 8 DO BEGIN "COL"
02600 IF ROW = ROOKROW THEN BEGIN "ONROW"
02700 IF COL = ROOKCOL THEN BEGIN
02800 PRINT("R");
02900 END ELSE BEGIN
03000 PRINT("*");
03100 END
03200 END "ONROW" ELSE BEGIN "OFFROW"
03300 IF COL = ROOKCOL THEN BEGIN
03400 PRINT("*");
03500 END ELSE BEGIN
03600 PRINT(".");
03700 END;
03800 END "OFFROW";
03900 END "COL";
04000 END "ROW";
04100
04200 END "MAIN";
We shall show the effects of making changes that leave the program
grammatically incorrect.
(1) Omitting an END, by deleting line 1100. When we execute the
program, we see the following on the terminal.
@EXECUTE (FROM) ROOK.SAI
ROOK.SAI.4 1
<C.CS10X>INTRO.HDR.1 1
<SAIL>IOSAIL.HDR.21 1
Fatal end of source file, scanning file.
BEGIN MAIN 00200/1
Last source-file macro: UPTO 02500/1
Current macro: UPTO
ROOK.SAI.4, PAGE 1
04100
The first line after the EXECUTE is the file ROOK.SAI.4 which was compiled,
followed by a 1 to show that the compiler was on page 1 of that file. The
next line shows that the introductory header was incorporated (by the
REQUIRE line). The third shows that the IOSAIL package in turn was REQUIREd
by INTRO. The fourth line is the error message; the compiler came to the end
of the ROOK.SAI file without having seen a complete program. The next line
shows that the incomplete structure was the BEGIN, labeled MAIN, on line
200 of page 1 (the only page) of the program. The next two lines are
irrelevant to this error. They refer to the fact that line 2500 uses UPTO
as an abbreviation for := 1 STEP 1 UNTIL .
(2) Failing to declare the variable COL ,
00400 INTEGER ROOKROW, ROOKCOL, ROW;
and omitting a semicolon
01700 PRINT("TRY AGAIN")
causes these error messages.
INSERTING FORGOTTEN SEMI-COLON.
ROOK.SAI.5, PAGE 1
01800 ROOKCOL
:= READ;
UNDECLARED IDENTIFIER: COL
ROOK.SAI.5, PAGE 1
02500 FOR COL
UPTO 8 DO BEGIN "COL"
IMPOSSIBLE TYPE COERCION
ROOK.SAI.5, PAGE 1
02700 IF COL = ROOKCOL THEN
BEGIN
IMPOSSIBLE TYPE COERCION
ROOK.SAI.5, PAGE 1
03300 IF COL = ROOKCOL THEN
BEGIN
End of compilation.
The first error causes multiple error messages, all at places where COL is
used. Notice that the errors were not discovered until the compiler had gone
a few symbols past COL in each case. The missing semicolon was automatically
restored; this is not always possible. The line 1800 is broken, continuing
on a lower line in the error message, after ROOKCOL ; that is where the
compiler was working when it found the error. Often, as in this case, the
actual error was on an earlier line.
(3) Inserting a space into a symbol
01400 ROOKCOL : = READ
(should be := ) and inserting a semicolon before ELSE
02900 END; ELSE BEGIN
causes these error messages:
SYNTAX ERROR. CURRENT STATEMENT OR DECLARATION WILL BE FLUSHED.
ROOK.SAI.6, PAGE 1
01400 ROOKCOL :
= READ;
STATEMENT FLUSHED.
EXTRANEOUS "ELSE", WILL BE IGNORED
ROOK.SA.6, PAGE 1
02900 END ; ELSE
BEGIN
End of compilation.
The first error was not diagnosed in detail. SYNTAX ERROR is a catchall
phrase for numerous grammatical problems. The error was discovered when the
compiler was looking at
ROOKCOL :
,however, which brings the reader's attention to the source of the problem.
The second error was diagnosed as resulting from an extra ELSE, rather than
an extra semicolon. As this indicates, you should not assume that error
messages tell you how to fix your program. They merely provide evidence
about what the compiler couldn't interpret.
(4) Leaving out an essential space
00800 WHILE ROOKROW < 1 OR ROOKROW > 8DO BEGIN
and using WHILE ... THEN instead of WHILE ... DO
01600 WHILE ROOKCOL < 1 OR ROOKCOL > 8 THEN BEGIN
causes these error messages:
ILLEGAL REAL CONSTANT
ROOK.SAI.7, PAGE 1
00800 WHILE ROOKROW < 1 OR ROOKROW > 8D
O BEGIN
ILLEGAL CONSTANT
ROOK.SAI.7, PAGE 1
00800 WHILE ROOKROW < 1 OR ROOKROW > 8D
O BEGIN
SYNTAX ERROR AT END OF EXPRESSION - WILL CHECK FOR PARENTHESES MISMATCH
ROOK.SAI.7, PAGE 1
00800 WHILE ROOKROW < 1 OR ROOKROW > 8DO
BEGIN
BLOCK FOUND WHILE FLUSHING STATEMENT - WILL TRY TO PARSE IT.
BLOCK END OKAY - FLUSH OF STATEMENT CONTINUES.
STATEMENT FLUSHED.
SYNTAX ERROR AT END OF EXPRESSION - WILL CHECK FOR PARENTHESES MISMATCH
ROOK.SAI.7, PAGE 1
01600 WHILE ROOKCOL < 1 OR ROOKCOL > 8 THEN
BEGIN
BLOCK FOUND WHILE FLUSHING STATEMENT - WILL TRY TO PARSE IT.
BLOCK END OKAY - FLUSH OF STATEMENT CONTINUES.
STATEMENT FLUSHED.
End of compilation.
The first shows that the compiler began to interpret 8 as a numerical
constant, then found the D in it and was confused. The same confusion
caused the next three error messages. You will often find that correcting
the first error in a program will make many error messages go away. The
last two error messages reflect the second error.
(5) Putting a declaration after a command, by putting line 400
(now line 650) after line 600.
00600 ROOKROW := READ;
00650 INTEGER ROOKROW, ROOKCOL, ROW, COL;
resulted in these error messages:
UNDECLARED IDENTIFIER: ROOKROW
ROOK.SAI.9, PAGE 1
00600 ROOKROW
:= READ;
CANNOT BEGIN A DECL OR STMNT LIKE THIS.
(MOST LIKELY A DECL AFTER A STMNT)
ROOK.SAI.9, PAGE 1
00650 INTEGER
ROOKROW, ROOKCOL, ROW, COL;
STATEMENT FLUSHED.
IMPOSSIBLE TYPE COERCION
ROOK.SAI.9, PAGE 1
00300 WHILE ROOKROW < 1 OR
ROOKROW, ROOKCOL, ROW, COL;
IMPOSSIBLE TYPE COERCION
ROOK.SAI.9, PAGE 1
00300 WHILE ROOKROW < 1 OR ROOKROW > 8 DO
BEGIN
Can't PRINT this syntactic type
ROOK.SAI.9, PAGE 1
01300 PRINT("ROW =", ROOKROW)
;
DRYROT -- GETAD
ROOK.SAI.9, PAGE 1
01300 PRINT("ROW =", ROOKROW)
;
The second message correctly diagnosed the problem. The compiler soon got
too confused to continue; this is what DRYROT means.
(6) Using = instead of := as the assignment operator
01800 ROOKCOL = READ;
and omitting a closing quote
02100 PRINT("COLUMN =, ROOKCOL, NEWLINE);
resulted in these errors:
SYNTAX ERROR. CURRENT STATEMENT OR DECLARATION WILL BE FLUSHED.
ROOK.SAI.11, PAGE 1
01800 ROOKCOL =
READ;
STATEMENT FLUSHED.
SYNTAX.ERROR. CURRENT STATEMENT OR DECLARATION WILL BE FLUSHED.
ROOK.SAI.11, PAGE 1
02400 FOR ROW UPTO 8 DO BEGIN "ROW
"
Fatal end of source file, scanning file.
BEGIN MAIN 00200/1
Last source-file macro: CLOSEALL 01400/1
Current macro: THRU
ROOK.SAI.11, PAGE 1
04200
The first message clearly reflects the first error. The compiler thought that
the quoted string in line 02100 went on up to the first quote in line 02400,
where it was immdiately followed by ROW, as if one had written
PRINT("XYZ" ROW... .
From here on, most of the program (except for block labels) was thoght to be
long quoted strings, so the ENDs were missed. At the end of the file,
therefore, there were still incomplete blocks. Omitting quote marks causes
very confusing error messages; check that every line includes an even number
of quote marks.
APPENDIX L. FINDING THE ROOT OF AN EQUATION.
For what value of X is COS(X) = X ? I.e., COS(X)-X = 0 . COS(0)-0 is
1 > 0 . COS(pi/2) - pi/2 is - pi/2 < 0 . Somewhere between,
COS(X)-X = 0 . We plan to narrow down the range in which the desired X lies,
by a factor of two at every step. Given two numbers LO and HI , where we
know that LO <= X (so COS(LO) - LO >= 0 ) and HI >= X (so
COS(HI) - HI <= 0 ), we take a number between them, MID = (HI + LO)/2 ,
and depending on whether COS(MID) - MID >= 0 or < 0 , we take MID as
the new value of HI or LO . We continue this until HI - LO is very small;
X always lies between them.
BEGIN
REAL LO, MID, HI;
LO := 0;
HI := 3.1416/2;
WHILE HI-LO > 0.000001 DO
BEGIN
COMMENT LO <= X <= HI, F(LO) >= 0, F(HI) >= 0;
MID := (HI+LO)/2;
IF COS(MID)-MID >= 0 THEN
LO := MID
ELSE HI := MID
COMMENT HI-LO HAS DECREASED BY HALF;
END;
PRINT("X SUCH THAT COS(X) = X IS", (HI+LO)/2)
END
The key to the above program is the invariant of the iteration: every time
we go through it, we start with a number in LO which is less than the
desired X , and a number in HI which is larger. Knowing this, it is easy
to find a new value for one or the other which is still on the correct side
of X , but is closer.
In order to know that the program will terminate, we have to see that
eventually, the difference between HI and LO will get less than any
positive number. (Actually, because of rounding errors, the difference may
only get down to about 10**-8 and just stay there; this is why the test
for termination was based on a number larger than 10**-8 .) It is very
important, when designing indefinite iterations, to be sure that they
won't go on forever.
APPENDIX M. POLYNOMIAL MULTIPLICATION.
Let A[0] + A[1]X + A[2]X**2 + ... + A[DA]X**DA and B[0] + B[1]X + ...
+ B[DB]X**DB be two polynomials. To get the coefficients of the product
polynomial, form the product of every monomial A[I]X**I from A , with
every monomial B[J]X**J from B . This contributes a term A[I]B[J]X**(I+J)
to the product, C , increasing C[I+J] by A[I]B[J] :
FOR K := 0 STEP 1 UNTIL DA + DB DO
C[K] := 0;
FOR I := 0 STEP 1 UNTIL DA DO
FOR J := 0 STEP 1 UNTIL DB DO
C[I+J] := C[I+J] + A[I] * B[J]
FOR K := 0 STEP 1 UNTIL DA + DB DO
PRINT(C[K],NEWLINE)
This organization of the nested iteration is much easier than trying to
compute each coefficient of C completely before going on to the next.
If you try to do so, you find that the program must consist of about
three separate nested iterations.
Suppose you want to raise a polynomial A to a power -- perhaps the fifth.
Schematically, one way to do it is:
Put A*A in B
Put A*B in C (i.e., A**3)
Put A*C in D (i.e., A**4)
Put A*D in E (i.e., A**5)
This entails writing out the nested loops for the multiplication four times.
It is much simpler to use another level of iteration: Start B off as the
polynomial 1 , and let the outer iteration successively change its value
to A , A**2 , A**3 , A**4 , A**5 . This is done, schematically, by:
Put 1 in B ;
FOR I := 1 STEP 1 UNTIL 5 DO
BEGIN
COMMENT ASSUME B IS A**(I-1)
Put A*B in C ;
Put C in B
COMMENT NOW B IS A**I
END
Writing the program out in detail,
BEGIN "MAIN"
REAL ARRAY A[0:10], B, C[0:50];
INTEGER DA, DB, DC, POWER;
COMMENT INPUT POLYNOMIAL A;
DA := READ;
FOR I := 0 STEP 1 UNTIL DA DO
A[I] := READ;
COMMENT PUT 1 IN B;
DB := 0;
B[0] := 1;
FOR POWER := 0 STEP 1 UNTIL 4 DO
BEGIN "POW"
DB := POWER * DA;
DC := DA + DB;
FOR K := 0 STEP 1 UNTIL DC DO C[K] := 0;
FOR I := 0 STEP 1 UNTIL DA DO
FOR J:= 0 STEP 1 UNTIL DB DO
C[I+J] := C[I+J] + A[I] * B[J];
COMMENT AB IS IN C;
FOR K := 0 STEP 1 UNTIL DC DO
B[K] := C[K]
END "POW"
END "MAIN"
The key to the above program is leaving the result of each iteration
(originally in array C ) in the place (array B ) where the input is
expected for the next iteration. Generally, if you want to iterate a
series of computations, you must match up its output with its own input.
[Into SAIL notes, insert before CONVERSION OF STRINGS TO NUMBERS.]
EXAMPLES OF STRING MANIPULATION IN SAIL.
In the following procedure bodies, it is assumed that the input is in string
variable S , and that string variable T and integer (or string) variable C
are available for use, along with integer variable L .
(1) To change the letters in a string to upper case:
BEGIN
INTEGER D;
T := NULL;
D := "A"-"a";
WHILE S NEQ NULL DO
BEGIN "MOVE"
C := LOP(S);
IF "a" <= C <= "z" THEN C := C+D;
T := T & C
END "MOVE"
END
(2) To change every occurrence of string X in S to a string Y :
BEGIN
T := NULL;
L := LENGTH(X);
WHILE LENGTH(S) >= L DO
BEGIN "MOVE"
IF EQU(S[1 FOR L],X) THEN
BEGIN
T := T & Y;
S := S[L+1 TO INF]
END
ELSE T := T & LOP(S)
END "MOVE"
RETURN(T & S)
END
(3) To test whether S is alphabetically earlier than T (returning
TRUE also if they are equal, and assuming that letters are all in
upper case):
BEGIN
WHILE S NEQ NULL OR T NEQ NULL DO
BEGIN
IF S = NULL THEN S := SPACE
ELSE IF T = NULL THEN T := SPACE;
IF S < T THEN RETURN (TRUE);
IF LOP(T) < LOP(S) THEN RETURN (FALSE)
END;
RETURN (TRUE)
END
(4) To remove initial, final, and multiple spaces from a string S :
BEGIN
T := NULL;
WHILE S = SPACE DO C := LOP(S);
WHILE S NEQ NULL DO
IF EQU(S[1 TO 2],"bb") THEN LOP(S)
ELSE T := T & LOP(S);
IF T[INF FOR 1] = SPACE
THEN RETURN (T[1 TO INF - 1])
ELSE RETURN (T)
END
(5) To insert N extra spaces in a string S as uniformly as possible
at the ends of words in order to expand the string. If S ends with
a word, no spaces are inserted after it.
BEGIN
T := NULL;
WHILE N NEQ 0 DO
BEGIN "SHIFTCHAR"
IF S = NULL THEN
BEGIN
S := T;
T := NULL
END;
C := LOP(S);
T := T & C;
IF C NEQ SPACE AND S = SPACE THEN
BEGIN "ADD SPACE"
T := T & SPACE;
N := N-1
END "ADD SPACE"
END "SHIFTCHAR"
END
(6) To remove from S , and return, the longest initial group of words of
not more than 50 characters.
BEGIN
IF LENGTH(S) <= 50 THEN
BEGIN
T := S;
S := NULL;
RETURN (T)
END;
N := 50;
WHILE S[N FOR 1] = SPACE OR S[N+1 FOR 1] NEQ SPACE DO
N := N-1;
T := S[1 TO N];
S := S[N+1 TO INF];
RETURN (T)
END
APPENDIX N. Number Representation on DEC System-20 and Relations to SAIL.
by John G. Herriot.
All numbers are stored in 36-bit words. The 36 bits of a word are numbered
from 0 to 35 , from left to right, just to identify them.
1. %Integers%.
Of the 36 bits in a word, bit 0 (the leftmost bit) represents the sign:
0 for positive and 1 for negative. In a positive number the remaining
35 bits are the magnitude of the number stored in a binary (base 2)
representation. For example, 21 (the subscript means base 10 ,
10
i.e., a decimal number) is stored as
000 000 000 000 000 000 000 000 000 000 010 101
↑
sign bit
(The digits are conventionally written in groups of three for ease of reading.
This grouping has no significance for the actual binary representation.)
To check this note that
34 5 4 3 2 1 0
21 = 0*2 + ... + 0*2 + 1*2 + 0*2 + 1*2 + 0*2 + 1*2 .
- - - - - - -
The largest positive integer which can be stored in a word is
34 33 1 0 35
2 + 2 + ... + 2 + 2 = 2 -1 = 34359738367 .
10
35
Any attempt to create or store an integer larger than 2 -1 will produce
erroneous results and the user will not always be warned of the error. Zero
is represented by a word containing all 0s.
To save space in writing words on paper, each group of 3 bits is frequently
converted to a single base-8 (octal) digit, according to the following code:
base 2 base 8 base 2 base 8
000 0 100 4
001 1 101 5
010 2 110 6
011 3 111 7
However, integers are actually stored as base-2 numbers.
Using octal notation, the decimal number 21 is represented by
000000000025 . Note that 25 is the octal representation of 21 .
8 8 10
Negative numbers have a sign bit of 1 and are stored in what is called
"two's complement form". First we define the %one's complement% of a number
in binary form as the result obtained by changing every 0 to 1 and every
1 to 0 . The %two's complement% of a number in binary form is obtained by
taking the one's complement of the portion of the number to the left of the
lowest order 1 and leaving the rest of the number unchanged. Notice that
taking the two's complement of the two's complement of a number restores the
original number. For example -1 is stored as
111 111 111 111 111 111 111 111 111 111 111 111
which may be written as 777777777777 . Also -21 is stored as
8
111 111 111 111 111 111 111 111 111 111 101 011
To check this, note that one can take the two's complement of this number,
obtaining the representation for +21 which can be evaluated as previously
35
explained. Alternatively one can regard the value of the sign bit as -2
and give the other digits their conventional values. Thus
35 34 5 4 3 2 1 0
-2 + 1*2 + ... + 1*2 + 0*2 + 1*2 + 0*2 + 1*2 + 1*2 = -21 .
- - - - - - -
The smallest integer which can be stored in the DEC System-20 is
35
-2 = -34359738368 and it is represented by 400000000000 . Note
10 8
that it cannot be produced by negating any positive number and that its
magnitude is one greater than the largest positive number. Remembering
that zero is represented by all 0s, we see that taking the negative of
this number means that no change is made becaup¬ there is no digit 1 .
Thus there is only one zero representation and its sign is positive.
Another way to think of the representation of negative numbers is to consider
a 36-place binary accumulating register (the base-2 equivalent of the decimal
accumulating register in a small calculator). If one starts with all zeros
in this register, one gets the representation for -1 by subtracting 1 .
The process requires a "borrow" to propagate to the left all the way across
the register, leaving all ones, just as on a decimal calculator this would
leave all nines. Continued subtractions will give the representations for
-2, -3, ... .
2. %Real Numbers%.
Numbers in many scientific computations will grow in magnitude well beyond
the range of integers described above. To provide for this, DEC System-20
and most scientific computers have a second way to represent numbers --
the so-called %floating-point representation%. The significance of the
name "floating-point" is that the %radix point% -- for example, the decimal
point in base-10 numbers -- is permitted to float to the right or left, thus
permitting scaling of numbers by various powers of the radix. Although a
decimal point that has floated off to the left will produce a number written
like 0.001345 , the numbers are actually represented in a form closer to what
-2
is often called %scientific notation%, here .1345*10 .
In DEC System-20 floating-point numbers are represented in base-2 notation,
i.e., the radix or number base is 2 . As in the case of integers, bit 0
(the leftmost bit) represents the sign: 0 for positive and 1 for negative.
The rest of the word represents an 8-digit exponent and a 27-bit fraction.
Bits 9 to 35 are interpreted as a binary fraction, i.e., 27 binary
digits with a binary point at the left-hand end. This part is called the
%mantissa%.
Bits 1 to 8 are interpreted as an integral exponent in excess 128 (200 )
8
code. This means that bits 1 - 8 may be thought of as giving the binary
(base-2) representation of a nonnegative integer in the range 0 to 255 ,
10 10
inclusive. This integer is called the %biased exponent% for reasons now to be
explained. If this integer were taken directly as the exponent, we would have
no negative exponents, and our range of floating-point numbers could not
-100
include such numbers as 2 . It is desirable to have an exponent range
which is approximately symmetric about zero. One obtains the %true exponent%
of the floating-point number by subtracting 128 from the biased exponent
represented by bits 1 to 8 ; this explains the name, excess 128 code. As
a result, the true exponents range from -128 to 127 .
As noted above, the 27 bits 9 to 35 are regarded as a binary fraction
with a binary point at the left-hand end. If the floating number zero is
being represented, all the bits are 0 . Otherwise, at least one of the binary
digits must be nonzero. A floating-point number is said to be %normalized% if
the left-hand binary digit (the most significant digit), bit 9 , is 1 . In
DEC System-20 the floating-point numbers are ordinarily normalized and we shall
not consider any other forms. Hence the mantissa, M , may be positive or
negative and its magnitude lies in the range 1/2 <= abs(M) < 1 .
Negative floating-point numbers are stored in two's complement form. Thus a
negative number has a 1 for its sign and the two's complement of the
mantissa. Since every fraction (except zero) ordinarily contains a 1 , it
has the one's complement of the exponent code in bits 1 to 8 .
We now give the floating-point representation of some sample numbers. As we
said before, the number zero is represented by 36 zero bits. Thus zero is
represented by the same word in floating-point or integer form. No other
number has this property. The number 1.0 is represented by the word
0 10 000 001 100 000 000 000 000 000 000 000 000
↑↑----------↑↑-----------------------------------↑
sign biased mantissa
bit exponent
To check this, note the sign is 0 (representing + ). The biased exponent
is 10000001 or 129 . Subtracting 128 yields 1 as the true
2 10 10
exponent. Putting a binary point at the left of the mantissa gives the binary
fraction whose value is 1/2 . (This binary fraction could be written more
concisely in octal form as .400000000 .) Thus the above word represents
8
+(1/2)*2 = 1.0 . To save writing, the above word may be written in octal
form 201400000000 . The number -1.0 is represented by the word
8
1 01 111 110 100 000 000 000 000 000 000 000 000
↑↑----------↑↑-----------------------------------↑
sign biased mantissa
bit exponent (two's complement)
(one's complement)
To check this, note that the sign is 1 (representing - ). The biased
exponent (after taking one's complement) is 10000001 = 129 and the true
10
exponent is 1 . Taking the two's complement of the mantissa we see that it
is unchanged (in this example) and its value is 1/2 . Thus the above word
represents -(1/2)*2 = -1.0 . It may be written in octal form
576400000000 .
8
Several examples of floating-point numbers are now given in octal notation,
with the confirmation left to the reader.
decimal floating-point (octal notation)
0.0 = 000000000000
1.0 = 201400000000
-1.0 = 576400000000
23.0 = 240560000000
-23.0 = 537220000000
0.0625 = 175400000000
-0.0625 = 602400000000
16.0 = 205400000000
-16.0 = 572400000000
256.0 = 211400000000
-256.0 = 566400000000
3.5 = 202700000000
-3.5 = 575100000000
153.0 = 210462000000
-153.0 = 567316000000
Notice that in checking the negative numbers one can take the two's complement
of the number in octal notation directly in the following way:
(i) take the seven's complement of all digits to the left of the lowest
order non-zero digit (i.e., subtract each digit from 7 )
(ii) take the eight's complement of the lowest order non-zero digit.
The largest floating-point number is 377777777777 representing
8
-27 127 39
(1-2 )*2 , approximately .178*10 . The smallest positive normalized
floating-point number is 000400000000 representing
8
-128 -129 -38
(1/2)*2 = 2 , approximately .140*10 . The negatives of these two
numbers are the extremes in magnitude of representable negative numbers.
They are represented by 100000000001 and 777400000000 respectively.
8 8
-27 -8
Since 2 is approximately equal to 10 , the precision of a 27 bit
-8
binary number is approximately 10 . Thus 27 binary bits are roughly
equivalent to 8 decimal digits.
Very few numbers can be exactly represented with 8 significant decimal digits.
For example, 1/80 = .012500000 is exactly represented, but
10
1/3 = .33333333 only approximately. Moreover, some numbers that are
exactly representable in decimal are only approximately representable in
binary; for example,
1/10 = .10000000 exactly, but
10
1/10 = .063146315 only approximately.
8
Conversely, some numbers that are exactly representable by 27 binary digits
are only approximately representable by 8 decimal digits. For example, the
floating-point number closest to 1.0 and above 1.0 has a mantissa,
M = .400000001
8
and an exponent 1 . Its value is
-26
1 + 2 = 1.000 000 014 901 161 193 847 656 25
10
or 1.0000000 to 8 significant digits. The floating-point number closest
to 1.0 and below 1.0 has a mantissa
M = .777777777
8
and an exponent 0 . Its value is
-27
1 - 2 = 0.999 999 992 549 419 403 076 171 875
or .99999999 to 8 significant figures.
Thus round-off enters into the representation of most floating-point numbers
on DEC System-20 and the round-off differs from that with decimal numbers.
This can easily give rise to unexpected results.
For example, if the number .70000000 is multiplied by 700 the result
10 10
is exact, that is 490.00000 . But if the number .70000000 is first
10 10
converted to 27-bit binary form, .546314632 , and if the integer 700 is
8 10
also converted to binary form, 1274 , then the product, rounded to 27 binary
8
bits is 752.000001 which is equivalent to 490.000004 . If the result is
8
printed out with only 7 significant digits, as is frequently done in SAIL,
it will appear as 490.0000 . But for purposes of comparison, the product
is greater than 490 and the Boolean expression product = 490 would be
FALSE. If the above calculation were performed in SAIL, the integer 700
10
would actually be converted to a normalized floating-point binary number,
10
.536000000 *2 and the product would be, after normalization,
8
9
.75200000 *2 which is the same as above, and consequently the same remarks
8
apply with respect to printing and comparisons.
3. %SAIL Arithmetic%.
When doing arithmetic with integers in SAIL, the operations, + , - , * ,
either give exact integer results, or else result in integers too large to
store in 35 bits (overflow) and cause an error halt. When the exponent
operation, ** , is applied to integers in SAIL the result is an integer
only if the exponent is a positive integer constant. In all other cases
the exponent is converted to a real floating-point number and the result
is floating point. When the division operation, / , is applied to integers
in SAIL, the integers are first converted to real floating point numbers and
the resulting quotient is floating point.
When arithmetic is done with real numbers in SAIL, the exact result may not be
representable either because it is too large or too small in magnitude or
because it cannot be represented by 27 binary bits. If the result is too
large, an error halt for overflow occurs. If the result is too small
(underflow), the result is given the value zero. If it cannot be represented
exactly, it is rounded to 27 bits (in normalized form) giving the closest
representable number. If the true result is X , then the calculated result
-27
(except in the case of underflow) is always between X*(1-2 ) and
-27
X*(1+2 ) . Naturally the accumulation of these small errors throughout
the steps of the program may often give rise to large errors in the final
result.
When a real value is assigned to an integer variable or vice versa, automatic
conversion is carried out.
When a real value, X , is assigned to an integer variable, if the magnitude
35 8
of the real number is greater than 2 -2 (= 34359738112) , then conversion
to integer will produce an invalid result but with no warning. If the
magnitude of X does not exceed this number then the converted integer
value is FLOOR(X) , which is the greatest integer less than or equal to X .
For example, FLOOR(4.9) = 4 , FLOOR(5.0) = 5 , FLOOR(5.1) = 5 ,
FLOOR(-4.9) = -5 , FLOOR(-5.0) = -5 , FLOOR(-5.1) = -6 .
When an integer value, N , is assigned to a real variable, if the integer
27
requires more than 27 bits of precision (2 = 134217728) , then some low
order significance will be lost in the conversion to real; otherwise,
conversion to real and then back to integer will result in the same integer
27
value. This means that if an integer value is less than 2 it will be
represented exactly as a floating-point number. But even if the integer
27
value exceeds 2 , it would be represented exactly if in its binary
representation the leftmost and rightmost ones are not more than 26 positions
apart.
When the two operands of a SAIL operation, + , - , * , / , ** , are of
different type, the integer operand is converted first to real type so that
the arithmetic is done as with real numbers.
Since the SAIL operations DIV and MOD force both operands to be integers
before dividing, real operands are first converted to integers as described
above, that is, real X is replaced by FLOOR(X) if X lies in the proper
range. Thus if X and Y are real numbers then
X DIV Y = (FLOOR(X)) DIV (FLOOR(Y))
= SIGN(FLOOR(X)/FLOOR(Y))*FLOOR(ABS(FLOOR(X)/FLOOR(Y)))
where SIGN(X) is -1 if X is negative and +1 otherwise. Also
X MOD Y = FLOOR(X) MOD FLOOR(Y)
= FLOOR(X)-(FLOOR(X) DIV FLOOR(Y))*FLOOR(Y) .
RANDOM NUMBERS.
SAIL contains a random number generator, which, on successive uses, gives a
series of numbers uniformly distributed between 0 and 1 . While the
numbers are not truly random, they satisfy most statistical tests for
randomness, and can be used to generate dice rolls, coin flips, and other
random events which might be wanted in a computer program.
The random number generator is ordinarily used once with a non-zero integer
argument, called the %seed%, to initialize it; the seed determines which
sequence of numbers it will generate. Thereafter it is used only with a zero
argument, each usage giving a new random number. To use the random number,
evaluate the expression RAN(e) , for any integer expression e ;
X := RAN(314159) initializes the generator with 314159 as the seed, and
also puts a random number into X ; thereafter, X := RAN(0) gives new
random numbers.
From the values of RAN(0) , most of the random numbers we might need can
be obtained. To get a random roll of the dice, we first multiply RAN(0)
by 6 (now it is a random number from 0 to 6 ), add 1 (now it is from
1 to 7 ), and take the integer part by assignment to an integer variable,
thus:
INTEGER DICE
.
.
.
X := RAN(71828)
.
.
.
DICE := 6 * RAN(0) + 1
.
.
.
For a random decimal digit (0 through 9) , it would be
INTEGER DIGIT;
DIGIT := 10 * RAN(0)
For a number uniformly distributed between -3 and 17 ,
REAL X;
X := 20 * RAN(0) - 3
For a number with a triangular distribution, use the smaller of two random
numbers:
X := RAN(0) MIN RAN(0)
or square a random number:
X := RAN(0) ** 2
For a normally distributed number (this distribution is the bell-shaped
curve beloved of statisticians), add twenty four random numbers obtained
from RAN. The resulting number, S , has mean 12 , variance 4 . To get
a number with mean M and variance V , use
(S-12) * .5 + M
Here is how RAN works. It uses one integer variable, which we will call R .
If, in the expression RAN(X) , X is not zero, R is initialized by
assigning X to it. Then R is multiplied by a certain constant, which
we will call K , and the low order 35 (?) bits are taken as the new value
of R . If K has been well chosen, the successive values of R behave
35 -35
like randomly selected integers in (0,2 -1) . Now R * 2 is returned
as the value of RAN(X) ; this number lies in the range 0 <= RAN(X) < 1 .
Example: to generate and print a random hand of 5 cards.
INTEGER SEED, I, CARD
INTEGER ARRAY USED[0:52];
SEED := 0;
WHILE SEED = 0 DO
BEGIN
PRINT ("TYPE IN NON-ZERO SEED FOR RANDOM NUMBER GENERATOR");
SEED := READ
END;
X := RAN(SEED);
FOR I UPTO 52 DO
USED[I-1] := 0;
USED[52] := 1
FOR I UPTO 5 DO
BEGIN
CARD := 52;
WHILE USED[CARD] = 1 DO
CARD := RAN(0) * 52;
USED[CARD] := 1;
PRINT ("A 2 3 4 5 6 7 8 9 10 J Q K "[(CARD REM 13)*2+1 FOR 2],
"OF", "CLUBS DIAMONDS HEARTS SPADES "
[(CARD DIV 4)*8 + 1 FOR 8])
END
The ideas of the above program are: A nonzero seed is obtained from the user.
The array USED keeps track (by 1's) of which cards (code numbers 0 to 51 )
have been used. A card code of 52 is an initialization convention to show
that no card has been picked yet. The first 13 card codes (0 to 12) are
clubs, the next 13 are diamonds, etc; CARD DIV 13 gives the suit number
(0 to 3). Card codes which are multiples of 13 are aces; codes one greater
are 2's, etc. CARD REM 13 gives the rank number (0 to 12).